package 第10周_冒泡排序_希尔排序和排序算法.第1章_冒泡排序法;

import 第1周_线性查找法.测试算法性能.ArrayGenerator;
import 第2周_排序基础.第一章选择排序法.SortingHelper;

import java.util.Arrays;

/**
 * 冒泡排序法
 */
public class BubbleSort {

    private BubbleSort(){}

    public static <E extends Comparable<E>> void sort(E[] data){

        for (int i = 0; i < data.length - 1; i++){
            for (int j = 0; j < data.length - i - 1; j++){
                if (data[j].compareTo(data[j + 1]) > 0){
                    swap(data, j, j + 1);
                }
            }
        }
    }

    public static <E extends Comparable<E>> void sort2(E[] data){

        for (int i = 0; i < data.length - 1; i++){
            boolean isSwappend = false;
            for (int j = 0; j < data.length - i - 1; j++){
                if (data[j].compareTo(data[j + 1]) > 0){
                    swap(data, j, j + 1);
                    isSwappend = true;
                }
            }
            if (!isSwappend){
                break;
            }
        }
    }

    public static <E> void swap(E[] data, int i, int j){
        E temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }

    public static void main(String[] args) {
        int n = 10000;

        Integer[] arr = ArrayGenerator.generateRandomArray(n, n);
        Integer[] arr2 = Arrays.copyOf(arr, arr.length);

        SortingHelper.sortTest("BubbleSort", arr);
        SortingHelper.sortTest("BubbleSort2", arr2);
    }
}
